package fun.coding.jeffreys.judge;

import java.util.Arrays;
import java.util.List;

import fun.coding.baozi.practice.BinaryTreeHelper;
import fun.coding.leetcode.TreeNode;

public class ConstructBinarySearchTreeFromPreorder {

	public static void main(String[] args) {
		ConstructBinarySearchTreeFromPreorder cbstfp = new ConstructBinarySearchTreeFromPreorder();
		
		int[] preTest1 = {10, 5, 2, 7, 15, 16};
		TreeNode rootTest1 = cbstfp.constructBstFromPreorder(preTest1);
		List<String> test1Actual = BinaryTreeHelper.serializeBinaryTree(rootTest1);
		String[] preTest1String = {"10", "5", "15", "2", "7", "#", "16"};
		// Assert with error message
		List<String> test1Expected = Arrays.asList(preTest1String);
		assert test1Expected.equals(test1Actual);
		
		int[] preTest2 = {10};
		TreeNode rootTest2 = cbstfp.constructBstFromPreorder(preTest2);
		List<String> test2Actual = BinaryTreeHelper.serializeBinaryTree(rootTest2);
		String[] preTest2String = {"10"};
		List<String> test2Expected = Arrays.asList(preTest2String);
		assert test2Expected.equals(test2Actual);
		
		int[] preTest3 = {10, 5, 7, 15, 13, 14};
		TreeNode rootTest3 = cbstfp.constructBstFromPreorder(preTest3);
		List<String> test3Actual = BinaryTreeHelper.serializeBinaryTree(rootTest3);
		String[] preTest3String = {"10", "5", "15", "#", "7", "13", "#", "#", "#", "#", "14"};
		List<String> test3Expected = Arrays.asList(preTest3String);
		assert test3Expected.equals(test3Actual);
		
		int[] preTest4 = {2, 3, 4};
		TreeNode rootTest4 = cbstfp.constructBstFromPreorder(preTest4);
		List<String> test4Actual = BinaryTreeHelper.serializeBinaryTree(rootTest4);
		String[] preTest4String = {"2", "#", "3", "#", "4"};
		List<String> test4Expected = Arrays.asList(preTest4String);
		assert test4Expected.equals(test4Actual);
	}
	
	
	/*
	 * 10， 5， 2， 7， 15， 16
	 * 
	 *          10 
     		5        15
   		  2   7    #    16
   		  
   		        10
   		    5        15    
   		      7    13
   		             14
   		             
   		10, 5, 7, 15, 13, 14             
	 * 
	 */
	public TreeNode constructBstFromPreorder(int[] pre) {
		
		return helper(pre, 0, pre.length - 1);
	}
	
	public TreeNode helper(int[] pre, int left, int right) {
		if (left > right) return null;
		
		TreeNode root = new TreeNode(pre[left]);
		
		int rightSubTreeIndex = right + 1;
		
		for (int i = left + 1; i <= right; i++) {
			if (pre[i] > pre[left]) {
				rightSubTreeIndex = i;
				break;
			}
		}
		
		root.left = helper(pre, left + 1, rightSubTreeIndex - 1);
		root.right = helper(pre, rightSubTreeIndex, right);
		
		
		return root;
	}

}
